/*
3.	Write down pseudo code to find out loop in a linked list and also find out starting node of loop.
*/
#include<iostream.h> // 40 minutes in completion , got stuck in the  finding start node , still not working , logic is absolutely right
#include<conio.h>

class Node 
{
      public:
             int data;
             Node *next;
             Node(int value)
             {
                      data = value;
                      next = NULL;
             }
};
class LinkedList
{
      public:
             Node *head, *tail;
             LinkedList()
             {
                 head = NULL;
                 tail = NULL;
             }
             void insert(int value);
   //          void removeDuplicate();
             void display();
             bool isLoop();
             int findLoopStart();
             void createLoop();
      private:
              void insert(Node **head, int value);
              void display(Node *head);
     //         void removeDuplicate(Node **head);
              bool isLoop(Node *head);
              int findLoopStart(Node *head);
              void createLoop(Node *tail);
};
int LinkedList :: findLoopStart(Node  *head)
{
    Node *slowPtr = head, *fastPtr = head;
    int loopExists = 1;
    while(slowPtr && fastPtr)
    {
         fastPtr = fastPtr->next;
         if(fastPtr == NULL)
         { 
              loopExists = 0;
              return -1;
         }
         if(fastPtr == slowPtr)
         {
             loopExists = 1;
             break;
         }
         fastPtr = fastPtr->next;
         if(fastPtr == NULL)
         {
             loopExists = 0;
             return -1;
         }
         if(fastPtr == slowPtr)
         {
              loopExists = 1;
              break;
         }
         slowPtr = slowPtr->next;//
//         if(fastPtr == slowPtr)
//               break;
    }
    if(loopExists)
    {
          slowPtr = head;
          while(slowPtr != fastPtr)
          {cout<<"1";
                     slowPtr = slowPtr->next;
                      fastPtr = fastPtr->next;
          }
    }
    return slowPtr->data;
}
int LinkedList :: findLoopStart()
{
     return  findLoopStart(head);
}
bool LinkedList :: isLoop(Node *head)
{
     Node *slowPtr = head, *fastPtr = head;
     while(slowPtr && fastPtr)
     {
          fastPtr = fastPtr->next;
          if(fastPtr == NULL)
               return   (fastPtr != NULL);
          if(fastPtr == slowPtr)
               return   (fastPtr == slowPtr);
          fastPtr = fastPtr->next;
          if(fastPtr == NULL)
            return (fastPtr != NULL);
          if(fastPtr == slowPtr)
             return fastPtr == slowPtr;
          slowPtr = slowPtr->next;
          if(slowPtr == fastPtr)
              return (slowPtr == fastPtr);        
     }
     
}
bool LinkedList :: isLoop()
{
    return isLoop(head);
}
void LinkedList :: insert(Node **head, int value)
{
     Node *newNode = new Node(value);
     if(*head == NULL)
     {
        *head = newNode;
        tail = newNode;
     }
     else
     {
         tail->next = newNode;
         tail = tail->next;
     }
}
void LinkedList :: insert(int value)
{
     insert(&head, value);
}
void LinkedList :: display(Node *head)
{
     Node *currNode = head;
     if(currNode == NULL)
         return ;
     while(currNode != NULL)
     {
         cout<<currNode->data<<"  " ;
         currNode = currNode->next;
     }
}
void LinkedList :: display()
{
     display(head);
}//
//void LinkedList :: removeDuplicat(Node ** head)
//{
//     Node *currNode = *head, *prevNode = *head;
//     if(*head == NULL)
//              return ;
//     while(currNode != NULL)
//     {
//          if(currNode->data != currNode->next->data)
//          {
//               currNode = currNode->next;
//          }
//          else 
//          {
//              while(currNode->data == currNode->next->data)
//              {
//                     prevNode->next = currnode->next;
//                     delNode = currNode;
//                     currNode = currNode->next;
//                     delete (delNode->next);
//                     
//              }
//          }
//     }
//     
//}
//void LinkedList :: removeDuplicate()
//{
//     removeDuplicate(&head);
//}'
void LinkedList :: createLoop(Node *tail)
{
     tail->next = head;
}
void LinkedList :: createLoop()
{
     createLoop(tail);
}
int main()
{
    LinkedList list;
    list.insert(10);
    list.insert(2);
    list.insert(4);
    list.insert(5);
    list.insert(10);
    list.insert(2);
    list.insert(5);
    list.display();
 //   list.createLoop();
 //   list.removeDuplicate();
//    list.display();
    cout<<"\n linked has loop "<<list.isLoop();
    cout<<"\nstarting node of loop "<<list.findLoopStart();
    getch();
    return 0;
}
